Content-Addressable Memories (CAMs) and Ternary Content-Addressable Memories (TCAMs) have been in use for some time. CAMs and TCAMs are routinely employed in various applications including, for example, lookup tables for IP (Internet Protocol) routers.
To facilitate discussion of CAMs and TCAMs, FIG. 1 shows a portion of an example prior art CAM 100 that is configured to decode an input pattern of 3 bits to a single match result. In a typical real world application, however, the number of bits may vary. Furthermore, CAMs may be implemented using different technologies although the basic functions described below are essentially the same for all CAMs.
In FIG. 1, there are shown three input lines B1, B2, and B3, representing the input lines for the input bits. The bit lines are intersected by a plurality of word compare circuits W1, W2, W3, etc . . . Since the example of FIG. 1 involves 3 input bits, there may be 23 or 8 possible word combinations and hence 8 possible word compare circuits W1-W8. In other implementations, there may be a greater or fewer number of word compare circuits than 2n (where n=number of input bits).
Each word compare circuit includes a plurality of bit compare circuits, with each bit compare circuit being associated with one of input bit lines B1-B3. Thus, in word compare circuit W1, there are three bit compare circuits 110, 112, and 114 corresponding to respective input bits B1, B2, and B3. Each of bit compare circuits 110, 112, and 114 includes a compare value storage cell and cell compare circuitry. For example, bit compare circuit 110 includes a compare value storage cell D1 and cell compare circuitry 122.
A compare value storage cell, such as compare value storage cell D1, is used to store one bit of data against which the corresponding input bit is compared. The comparison is performed by the associated cell comparison circuitry (so that cell comparison circuitry 122 would be employed to compare input bit B1 against the data value stored in compare value storage cell D1, for example).
In a typical implementation, the compare value storage cells of CAMs (such as compare value storage cell D1) is implemented using SRAM (Static Random Access Memory) technology. SRAM technology is typically employed due to the high density offered. Generally speaking, TCAMs also employ SRAM technology for their compare value storage cells and mask value storage cells for the same reason. The bit compare circuit may be implemented using a combination of an XNOR gate and an AND gate connected as shown in cell compare circuitry 122. The inputs for each AND gate (such as AND gate 130 of cell compare circuit 112) are taken from the output of the associated XNOR gate (such as XNOR gate 132) and the output of the previous bit compare circuit (such as bit compare circuit 110). If there is no output from the previous bit compare circuit, a value “1” is used (as can be seen with AND gate 140).
Suppose that the three compare value storage cells associated with word compare circuit W1 store the bit pattern “101”. This bit pattern “101” is compared against the bit pattern inputted into bit lines B1-B3. If the input bit pattern presented on bit lines B1-B3 is also “101”, the comparison result against the data values stored in word compare circuit W1 would be a match, and the output 160 of word compare circuit W1 would be active. Any word compare circuit whose stored bit pattern is different from “101” would have an inactive output. On the other hand, if the input bit pattern presented on bit lines B1-B3 is “111”, the comparison result against the data values stored in word compare circuit W1 would not be a match, and the output 160 of word compare circuit W1 would be inactive. The word compare circuit whose stored bit pattern is “111” would have an active output.
As can be seen, CAM 100 returns at most a single match (W1 . . . WN) for a given input bit pattern (assuming that a unique input bit pattern is loaded or stored in each word compare circuit). The match (W1 . . . WN) may then be encoded to an address of the matched word.
TCAMs are similarly constructed as seen in FIG. 2. A TCAM offers the ability to mask certain input bits per entry, turning these input bits into “don't care” bits. For example, whereas the input bit pattern “011” would yield a single match using a CAM, it is possible to specify that the first bit “0” is a “don't care” for a specific entry. In this case, the first bit is said to be “masked” during the comparison process, and the result matches against either stored bit pattern “111” or “011”. For TCAMs, it is common for multiple entries to match, and the first match is typically selected and the address of the first match encoded.
The difference between FIG. 2 (TCAM) and FIG. 1 (CAM) is the presence of the mask bit storage cells M1, M2, and M3, and the extra OR gates 202, 204, and 206. Each OR gate is inserted between the output of the XNOR gate and the input of the AND gate in each bit compare circuit. For example, OR gate 204 has two inputs: the output of XNOR gate 132 and the value of the mask bit in mask bit storage cell M1. It should be apparent to one skilled in the art that when the mask bit is “0”, the associated TCAM bit storage circuit functions in the same manner as the CAM bit storage circuit of FIG. 1. When the mask bit is “1”, the associated TCAM bit storage circuit implements the “don't care” function.
As mentioned, both CAMs and TCAMs are implemented using SRAM technology. SRAM technology, as is known, suffers from soft errors, which is attributed to the presence of naturally occurring alpha particles. SRAM memory chips, which are employed to store data for use by computer applications and/or the operating system, may employ error correcting code (ECC) or parity bits for the stored words. For example, a parity bit may be stored for each data word written into the SRAM memory chip. Parity checking may be performed after reading the stored data word from the SRAM memory to ensure data integrity. By checking for parity, a soft error on one of the stored bits can be detected before a stored data word is utilized.
With CAMs and TCAMs, error detection is more difficult since the corruption of one or more bits may still yield a match output, albeit the wrong match output. For example, if a stored bit pattern “101” is corrupted and becomes “001” due to a soft error on the most significant bit, inputting a bit pattern of “001” may yield a match output, albeit a match output that is due to soft error. The input bit pattern “101” may yield a “no match” result, which is also a legitimate output for CAMs and TCAMs. Thus, unlike SRAM memory chips, the outputs of CAMs and TCAMs (which reflect a match or no match) do not lend themselves to parity checking easily. This is because the output of a CAM/TCAM is either a no-match or a match (which is then decoded into an output address) instead of the stored bits themselves (as in the case with SRAMs). Accordingly, performing parity/ECC on the CAM/TCAM output would not reveal the data corruption that occurs to the stored bit pattern inside the CAM/TCAM. This is in contrast to the case with SRAM, whereby the output is the read stored bit pattern itself and parity/ECC can be applied to the stored bit pattern read from memory prior to use.
Data corruption is also exacerbated as the device geometries shrink. As devices become smaller, the compare value storage cells and/or the mask bit storage cells become more susceptible to data corruption. Additionally, as CAMs and TCAMs become denser and include a larger number of storage cells, the probability of corruption to one of the stored compare value bits or stored mask bits increases. Furthermore, as manufacturers pack more devices into smaller form factors, devices are being placed near and/or under area bumps (i.e., the connection points to connect the chip to the outside world). It has been found that storage cells near and/or under the area bumps tend to suffer a higher rate of soft errors.
Because of the increased likelihood of soft errors, manufacturers have become concerned over CAM and TCAM reliability. To the inventor's knowledge, the solution thus far has been to periodically reload the CAMs and TCAMs with fresh compare values and/or fresh mask bit values. However, this approach is inefficient since the CAMs/TCAMs are essentially unusable during the loading process. Furthermore, from the time the soft error occurred until the CAM/TCAM is reloaded, incorrect results may occur.
In view of the foregoing, improved solutions for managing soft errors in CAMs/TCAMs are needed.